package 实验三_线性链表的实现和应用;

/**
 * by 孙彪 2215805342 2025.3.20
 *  线性链表的实现和应用
 */

public class Test {
    // 定义链表的节点类
    static class Node {
        String data;
        Node next;

        Node(String data) {
            this.data = data;
            this.next = null;
        }
    }

    // 单链表类
    static class LinkedList {
        private Node head;

        // 添加节点到链表尾部
        public void add(String data) {
            Node newNode = new Node(data);
            if (head == null) {
                head = newNode;
            } else {
                Node cur = head;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = newNode;
            }
        }

        // 根据1开始的索引查找节点，返回节点数据
        public String find(int index) {
            Node cur = head;
            int count = 1;
            while (cur != null) {
                if (count == index) {
                    return cur.data;
                }
                count++;
                cur = cur.next;
            }
            return null;  // 如果不存在则返回 null
        }

        // 根据1开始的索引删除节点，返回 true 删除成功，否则返回 false
        public boolean delete(int index) {
            if (head == null || index < 1) {
                return false;
            }
            if (index == 1) {
                head = head.next;
                return true;
            }
            Node cur = head;
            int count = 1;
            // 找到第 index-1 个节点
            while (cur != null && count < index - 1) {
                cur = cur.next;
                count++;
            }
            // 如果 cur 为空或者 cur.next 为空，则说明 index 不存在
            if (cur == null || cur.next == null) {
                return false;
            }
            cur.next = cur.next.next;
            return true;
        }

        // 以指定格式输出链表所有数据
        public void printList() {
            Node cur = head;
            StringBuilder sb = new StringBuilder();
            while (cur != null) {
                sb.append(cur.data);
                if (cur.next != null) {
                    sb.append("->");
                }
                cur = cur.next;
            }
            System.out.println(sb.toString());
        }
    }

    public static void main(String[] args) {
        // 创建链表并添加数据（数据内容可自行修改）
        LinkedList list = new LinkedList();
        list.add("a");
        list.add("b");
        list.add("c-z");
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        list.add("e");
        list.add("F");
        list.add("S");

        // 输出初始链表
        System.out.print("链表中的数据：");
        list.printList();

        // 按照要求查找指定位置的元素，索引从1开始
        int[] searchIndexes = {2, 5, 7, 8, 9};
        for (int index : searchIndexes) {
            String value = list.find(index);
            System.out.println("查找：第" + index + "个字符是" + value);
        }

        // 刪除第1个元素
        if (list.delete(1)) {
            System.out.print("刪除第1个元素后，链表状态为：");
            list.printList();
        }

        // 刪除第3个元素
        if (list.delete(3)) {
            System.out.print("刪除第3个元素后，链表状态为：");
            list.printList();
        }

        // 删除第6个元素
        if (list.delete(6)) {
            System.out.print("删除第6个元素后，链表状态为：");
            list.printList();
        }

        // 尝试删除第11个元素（此时链表长度不足）
        if (!list.delete(11)) {
            System.out.println("Error！删除第11个元素不存在！");
        }
    }


}
